package com.atguigu.sort;

import java.util.Arrays;

public class QuickSortByMe {
    public static void main(String[] args) {
        int[] a=new int[]{40, 33, 15, 51, 54, 78, 49, 91, 38, 28};
        System.out.println(Arrays.toString(a));
        quickSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
    public static void quickSort(int[] a,int L,int R){
        if(L>=R) return;
        swap(a,(int)(Math.random()*(R-L+1)+L),R);
        int[] p=partition(a,L,R);
        quickSort(a,L,p[0]);
        quickSort(a,p[1]+1,R);
    }
    public static int[] partition(int[] a,int L,int R){
        //波兰国旗问题
        int left=L-1; //小于区边界
        int right=R; //大于区边界
        while(L<right){
            if(a[L]<a[R]){
                swap(a,left+1,L);
                left++;
                L++;
            }else if(a[L]>a[R]){
                swap(a,right-1,L);
                right--;
            }else{
                L++;
            }
        }
        swap(a,right,R);
        return new int[]{left+1,right};
    }
    public static void swap(int[] a,int i,int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
}
